//160.相交链表
//给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。
//如果两个链表不存在相交节点，返回 null 。

#include <stdio.h>

struct ListNode 
{
    int val;
    struct ListNode *next;
};

//双指针法
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    //若有一个链表为空，则无相交点，返回空
    if(headA == NULL || headB == NULL)
        return NULL;
    
    struct ListNode *head1 = headA;
    struct ListNode *head2 = headB;

    //想要找到相交点则两个链表移动的距离是相同的
    //链表A：a+c   链表B：b+c   则链表移动：a+b+c
    //所以当有一个链表为空时，就重新指向另一个链表的头部，继续移动，直到找到相交点
    while(head1 != head2)
    {
        if(head1 == NULL)
            head1 = headB;
        else
            head1 = head1->next;

        if(head2 == NULL)
            head2 = headA;
        else    
            head2 = head2->next;
    }

    return head1;
}